class Solution(object):
    def minFlips(self, mat):
        m = len(mat)
        n = len(mat[0])
        val = 0
        for i in range(m * n):
            x, y = i // n, i % n
            if mat[x][y] == 1:
                val |= (1 << i)
        st = {val}
        if val == 0:
            return 0
        cost = 0
        already = {val}
        while st:
            next_st = set()
            cost += 1
            for node in st:
                for i in range(m * n):
                    next_node = node
                    x, y = i // n, i % n
                    next_node ^= (1 << i)
                    for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                        if 0 <= ux < m and 0 <= uy < n:
                            next_node ^= (1 << (ux * n + uy))
                    if next_node not in already:
                        if next_node == 0:
                            return cost
                        already.add(next_node)
                        next_st.add(next_node)
            st = next_st
        return -1


data = Solution()
mat = [[1,0,0],[1,0,0]]
print(data.minFlips(mat))